//给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 
//
// 
//
// 示例 1： 
//
// 
//输入:a = "11", b = "1"
//输出："100" 
//
// 示例 2： 
//
// 
//输入：a = "1010", b = "1011"
//输出："10101" 
//
// 
//
// 提示： 
//
// 
// 1 <= a.length, b.length <= 10⁴ 
// a 和 b 仅由字符 '0' 或 '1' 组成 
// 字符串如果不是 "0" ，就不含前导零 
// 
//
// Related Topics 位运算 数学 字符串 模拟 👍 1259 👎 0


package LeetCode.editor.cn;

import java.math.BigInteger;

/**
 * @author ldltd
 * @date 2024-12-12 23:08:10
 * @description 67.二进制求和
 */
public class AddBinary{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 AddBinary fun=new AddBinary();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public String addBinary1(String a, String b) {
		StringBuilder ans = new StringBuilder();
		int ca = 0;
		for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
			int sum = ca;
			sum += i >= 0 ? a.charAt(i) - '0' : 0;
			sum += j >= 0 ? b.charAt(j) - '0' : 0;
			ans.append(sum % 2);
			ca = sum / 2;
		}
		ans.append(ca == 1 ? ca : "");
		return ans.reverse().toString();
	}
	//超限了，用大数
	public String addBinary2(String a, String b) {
		// 将字符串转换为二进制的整数
		BigInteger x = new BigInteger(a, 2);
		BigInteger y = new BigInteger(b, 2);

		while (!y.equals(BigInteger.ZERO)) {
			// 使用异或计算结果
			BigInteger answer = x.xor(y);
			// 计算进位
			BigInteger carry = x.and(y).shiftLeft(1);
			// 更新 x 和 y
			x = answer;
			y = carry;
		}

		// 将结果转换回二进制字符串
		return x.toString(2);
	}
		/*把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
		当进位不为 0 时
		计算当前 x 和 y 的无进位相加结果：answer = x ^ y
		计算当前 x 和 y 的进位：carry = (x & y) << 1
		完成本次循环，更新 x = answer，y = carry
		返回 x 的二进制形式

		0 ^ 0 = 0（两个 0 相加为 0）
		1 ^ 0 = 1 或 0 ^ 1 = 1（1 和 0 相加为 1）
		1 ^ 1 = 0（两个 1 相加为 0，但产生了进位）
		异或代表了二进制加法中无进位的部分，最后一位一定准确
		(x & y) << 1)：计算进位
		1 & 1 = 1（两个 1 相加会产生进位）
		1 & 0 = 0 或 0 & 1 = 0（其他情况不会产生进位）
		可以计算最后两位相加是否进位，然后左移一位，可以在下一位起作用


		二进制加法本质上是对每个位进行加法，
		其中需要处理无进位加法和进位。
		这个算法准确地将这两部分分离，分别通过异或和位与实现。
		*/
	public String addBinary(String a, String b) {
		// 将字符串转换为二进制的整数
		int x = Integer.parseInt(a, 2);
		int y = Integer.parseInt(b, 2);

		while (y != 0) {
			// 使用异或计算结果
			int answer = x ^ y;
			// 计算进位
			int carry = (x & y) << 1;
			// 更新 x 和 y
			x = answer;
			y = carry;
		}

		// 将结果转换回二进制字符串
		return Integer.toBinaryString(x);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
